package tree;

/**
 * 找二叉树中序遍历的下一个节点
 */
public class FindNextNode {

  public TreeNode findNextNode(TreeNode node) {

    if (node == null) {
      return null;
    }

    TreeNode next = null;
    //如果存在右子树，找右子树的第一个节点
    if (node.getRight() != null) {
      next = node.getRight();
      while (next.getLeft() != null) {
        next = next.getLeft();
      }
      return next;
    }

    //如果不存在右子树，第一种情况，当前节点是他的父节点的子节点
    //第二种情况，一直向上找
    TreeNode parent = node.getParent();
    while (parent != null) {
      if (parent.getLeft() == node) {
        return parent;
      }
      parent = parent.getParent();
    }

    return next;
  }


  public static void main(String args[]) {
    TreeNode A = new TreeNode('A');
    TreeNode B = new TreeNode('B');
    TreeNode C = new TreeNode('C');
    TreeNode D = new TreeNode('D');
    TreeNode E = new TreeNode('E');
    TreeNode F = new TreeNode('F');
    TreeNode G = new TreeNode('G');

    A.setLeft(B);
    A.setRight(C);
    B.setLeft(D);
    B.setRight(E);
    E.setLeft(G);
    C.setRight(F);

    FindNextNode findNextNode = new FindNextNode();
    TreeNode next = findNextNode.findNextNode(F);
    if (next != null) {
      System.out.println(next.getValue());
    } else {
      System.out.println("找不到下一个节点");
    }
  }
}
